import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25397
 * Date: 2022-01-17
 * Time: 15:34
 */
class BTNode{//节点
    public int val;
    public BTNode left;//左孩子的引用
    public BTNode right;//右孩子的引用
    public BTNode(char val){
        this.val=val;
    }
}
public class BinaryTree {//二叉树类
    public BTNode root;//二叉树根节点
    public BTNode createTree(){
        BTNode A=new BTNode('A');
        BTNode B=new BTNode('B');
        BTNode C=new BTNode('C');
        BTNode D=new BTNode('D');
        BTNode E=new BTNode('E');
        BTNode F=new BTNode('F');
        BTNode G=new BTNode('G');
        BTNode H=new BTNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }

    //前序遍历——根左右
    void preOrder(BTNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历——左根右
    void inOrder(BTNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    //后序遍历——左右根
    void postOrder(BTNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //层序遍历，一层一层往下



    //获取树中节点个数
    //遍历思路：定义一个计数器count，遍历二叉树，如果是节点，则count++，遍历方法前中后序都可以
    /*int count=0;//count不能放到函数里面，因为你放到函数里面，每次递归都会变成0
    int size(BTNode root){
        if(root==null){
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }*/

    //子问题思路：左树节点+右树节点=整棵树节点
    int size(BTNode root){
        if(root==null){
            return 0;
        }else{
            return size(root.left)+size(root.right)+1;
        }
    }

    //获取叶子节点个数
    //遍历思路：遍历到叶子节点，count++
    /*int count=0;
    int getLeafNodeCount(BTNode root){
        if(root==null){
            return 0;
        }else if(root.left==null&&root.right==null){
            count++;
            return count;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return count;
    }*/

    //子问题思路：左树的叶子+右树的叶子=整棵树叶子
    int getLeafNodeCount(BTNode root){
        if(root==null){
            return 0;
        }else if(root.left==null&&root.left==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    //获取第k层节点个数
    //思路：求第K层节点个数，就是求左子树第k-1层和右子树第k-1层个数和
    int getKLevelNodeCount(BTNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    //获取二叉树的高度
    //思路：左数高度和右树高度比较，取最大值，最后+1（最大值是子树高度，还要算上根）
    int getHeight(BTNode root){
        if(root==null){
            return 0;
        }else{
            int maxLeft=getHeight(root.left);
            int maxRight=getHeight(root.right);
            return maxLeft>maxRight?maxLeft+1:maxRight+1;
            //return getHeight(root.left)>getHeight(root.right)?getHeight(root.left)+1:getHeight(root.right)+1;
            //三目运算符，左树高度比右树高度大，就返回左数高度，否则就是右树高度，最后+1
            //三目运算符这种写法，在树比较大的时候时间复杂度很大（重复递归了左树和右树最大高度），建议还是上面的写法
        }
    }

    //检测值为value的节点是否存在
    //思路：遍历二叉树中的节点，判断该节点中有没有我要找到数据，如果没有就去子树找（先左还是先右你自己选）
    BTNode find(BTNode root,int val){
        if(root==null){
            return null;
        }else if(root.val==val){
            return root;
        }else{
            BTNode ret1=find(root.left,val);
            if(ret1!=null){//!=null说明找到了
                return ret1;
            }
            BTNode ret2=find(root.right,val);
            if(ret2!=null){
                return ret2;
            }
            //走到这里还是没有return出去，说明左右子树都没有找到
            return null;
        }
    }

    //判断一个树是不是完全二叉树
    boolean isCompleteTree(BTNode root){
        if(root==null){
            return true;
        }
        Queue<BTNode>queue=new LinkedList<>();
        queue.offer(root);//offer效果和add一样，向队列里面添加元素
        while(!queue.isEmpty()){
            BTNode cur= queue.poll();//弹出队列首个元素，赋值给cur
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()){//判断队列里面的剩余元素是不是全空（全空为完全二叉树，不然就不是）
            BTNode top= queue.peek();//取队头元素（不删除）
            if(top!=null){
                return false;
            }
            queue.poll();//弹出队头元素（删除）
        }
        return true;//走完while说明原先队列剩余元素都是null，也就是完全二叉树
    }

    //层序遍历
    //思路，创建一个队列，往队列里面放根节点，然后出掉根节点，放入左右结点，
    //出掉队头节点，放入队头节点左右节点
    //出掉队头节点，放入队头节点左右节点
    //出掉队头节点，放入队头节点左右节点
    //...
    public void levelOrder(BTNode root){
        if(root==null){
            return ;
        }
        Queue<BTNode>queue=new LinkedList<>();
        queue.offer(root);//offer效果和add一样，向队列里面添加元素
        while(!queue.isEmpty()){
            BTNode cur= queue.poll();//弹出队列首个元素，赋值给cur
            if(cur!=null){
                System.out.print(cur.val+" ");
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
    }

    /*public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        BTNode root=binaryTree.createTree();
        binaryTree.preOrder(root);//A B D E H C F G

        System.out.println();
        binaryTree.inOrder(root);//D B E H A F C G

        System.out.println();
        binaryTree.postOrder(root);//D H E B F G C A

        System.out.println();

        int size=binaryTree.size(root);
        System.out.println(size);//打印8

        int LeafNodeCount= binaryTree.getLeafNodeCount(root);
        System.out.println(LeafNodeCount);//4

        int getKLevelCount= binaryTree.getKLevelNodeCount(root, 3);
        System.out.println(getKLevelCount);//4

        int height= binaryTree.getHeight(root);
        System.out.println(height);//4

        BTNode ret1= binaryTree.find(root,'c');
        System.out.println(ret1);//null
        BTNode ret2= binaryTree.find(root,'C');
        System.out.println(ret2);//BTNode@1b6d3586（C地址）
        System.out.println(ret2.val);//C

        boolean isC=binaryTree.isCompleteTree(root);
        System.out.println(isC);
    }*/


    void preOrderNor(BTNode root){//非递归前序遍历——仍然是根左右的顺序
        Stack<BTNode> stack=new Stack<>();
        BTNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            //到这里左走完了
            BTNode top= stack.pop();//树最左边的节点——没有左子树了
            cur=top.right;
            //看看有没有右节点——有右节点，外面的while会继续向右遍历
            //没有右节点，外面的while会依次出掉栈顶的元素，实现递归的“归”
        }
    }

    void inOrderNor(BTNode root){//非递归前序遍历——仍然是根左右的顺序
        Stack<BTNode> stack=new Stack<>();
        BTNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //到这里左走完了
            BTNode top= stack.pop();//树最左边的节点——没有左子树了
            System.out.print(top.val+" ");
            cur=top.right;
            //看看有没有右节点——有右节点，外面的while会继续向右遍历
            //没有右节点，外面的while会依次出掉栈顶的元素，实现递归的“归”
        }
    }

    void postOrderNor(BTNode root){//非递归前序遍历——仍然是根左右的顺序
        Stack<BTNode> stack=new Stack<>();
        BTNode cur=root;
        BTNode prev=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //到这里左走完了
            BTNode top= stack.peek();//树最左边的节点——没有左子树了
            //如果当前节点的右子树被打印过或者遍历过，直接就可以弹出了
            if(top.right==null||top.right==prev){
                stack.pop();
                System.out.print(top.val+" ");
                prev=top;//记录一下，最近一次打印的节点
            }else{
                cur=top.right;
            }
            //看看有没有右节点——有右节点，外面的while会继续向右遍历
            //没有右节点，外面的while会依次出掉栈顶的元素，实现递归的“归”
        }
    }

    /*public static void main(String[] args) {

        BinaryTree binaryTree=new BinaryTree();
        BTNode root=binaryTree.createTree();
        binaryTree.preOrderNor(root);//A B D E H C F G
        System.out.println();

        binaryTree.inOrderNor(root);//D B E H A F C G
        System.out.println();

        binaryTree.postOrderNor(root);
    }*/

    public int widthOfBinaryTree(BTNode root) {//获取二叉树最大宽度-力扣622
        //层序遍历,对每个节点标号
        //因为题目中数的值是没有用的,我们可以依次进行编号，然后用每层最右边的值-每层最左边的值+1，就可以得到需要的宽度
        //对于最大宽度，让各层的比较一下即可
        if(root==null){
            return 0;
        }
        LinkedList<BTNode>queue=new LinkedList<>();
        int maxWidth=0;
        root.val=0;
        queue.offer(root);//offer效果和add一样，向队列里面添加元素
        while(!queue.isEmpty()){
            BTNode cur= queue.poll();//弹出队列首个元素，赋值给cur
            int count=queue.size();//当前队列中节点个数
            int width=queue.getLast().val-queue.getFirst().val+1;
            if(cur.left!=null){
                queue.offer(cur.left);
                cur.left.val=cur.val*2+1;//左子树下标为根的2倍加1
            }
            if(cur.right!=null){
                queue.offer(cur.right);
                cur.left.val=cur.val*2+2;//右子树下标为根的2倍加2
            }
            else {
                break;
            }
            if(width>maxWidth){
                maxWidth=width;
            }
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        BTNode root=binaryTree.createTree();
        int i=binaryTree.widthOfBinaryTree(root);
        System.out.println(i);
    }
}




